﻿#define _CRT_SECURE_NO_WARNINGS 1
//定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
//
//不允许修改 链表。
//
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//法一
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* cur1 = head;
//    int pos1 = 0;
//    while (cur1)
//    {
//        struct ListNode* cur2 = head;
//        int pos2 = 0;
//        while (cur2)
//        {
//            if (cur2 == cur1)
//            {
//                if (pos1 == pos2)
//                    break;
//                else
//                {
//                    return cur1;
//                }
//            }
//            cur2 = cur2->next;
//            pos2++;
//        }
//        cur1 = cur1->next;
//        pos1++;
//    }
//    return NULL;
//
//
//}
//法二
//方法二：快慢指针
//思路与算法
//
//我们使用两个指针，\textit{ fast }fast 与 \textit{ slow }slow。它们起始都位于链表的头部。随后，\textit{ slow }slow 指针每次向后移动一个位置，而 \textit{ fast }fast 指针向后移动两个位置。如果链表中存在环，则 \textit{ fast }fast 指针最终将再次与 \textit{ slow }slow 指针在环中相遇。
//
//如下图所示，设链表中环外部分的长度为 aa。\textit{ slow }slow 指针进入环后，又走了 bb 的距离与 \textit{ fast }fast 相遇。此时，\textit{ fast }fast 指针已经走完了环的 nn 圈，因此它走过的总距离为 a + n(b + c) + b = a + (n + 1)b + nca + n(b + c) + b = a + (n + 1)b + nc。
//
//
//
//根据题意，任意时刻，\textit{ fast }fast 指针走过的距离都为 \textit{ slow }slow 指针的 22 倍。因此，我们有
//
//a + (n + 1)b + nc = 2(a + b) \implies a = c + (n - 1)(b + c)
//a + (n + 1)b + nc = 2(a + b)⟹a = c + (n−1)(b + c)
//
//有了 a = c + (n - 1)(b + c)a = c + (n−1)(b + c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n - 1n−1 圈的环长，恰好等于从链表头部到入环点的距离。
//
//因此，当发现 \textit{ slow }slow 与 \textit{ fast }fast 相遇时，我们再额外使用一个指针 \textit{ ptr }ptr。起始，它指向链表头部；随后，它和 \textit{ slow }slow 每次向后移动一个位置。最终，它们会在入环点相遇。

//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* slow = head, * fast = head;
//    while (fast != NULL) {
//        slow = slow->next;
//        if (fast->next == NULL) {
//            return NULL;
//        }
//        fast = fast->next->next;
//        if (fast == slow) {
//            struct ListNode* ptr = head;
//            while (ptr != slow) {
//                ptr = ptr->next;
//                slow = slow->next;
//            }
//            return ptr;
//        }
//    }
//    return NULL;
//}
